 # 变量命名特点：所有单个单词首字母小写，所有两个单词连写则第一个首字母小写，第二个首字母大写。
class Vertex:
    '''将每个棋盘状况做成节点，包括当前轮到谁的信息等等。'''
    def __init__(self,board,belong,player,currentRound=None,mode=None,parent=None):
        self.board = board # 棋盘
        self.belong = belong # 当前棋局（即将）行动方
        self.player = player # 玩家自己（即Player类）
        self.round = currentRound # 当前轮数
        self.mode = mode # 当前模式
        self.parent = parent # 父节点
        self.child = {} # 子节点的字典：{做出的行动:子节点}
        self.orderedMove = [] # 根据行动方的对手还是自己，将考虑的行动排序，更有效剪枝。
        self.alpha = float('-inf') # 下界
        self.beta = float('inf') # 上界
        self.boardValue = self.player.cost_function_2(board) # 静态估值函数，先用这个凑合一下，要更改函数只需要改此一处。
        self.searchValue = None # 搜索后估值
        self.bestchoice = None # （行动方）最佳策略
        
    def setRange(self,alpha,beta):
        self.alpha = alpha
        self.beta = beta
        
    def expand(self):
        '''生成当前节点的子节点'''
        if self.mode == 'position':
            another = self.board.getNext(self.belong,self.round)
            available = self.board.getNone(not self.belong)
            if another != ():
                imitation = self.board.copy()
                imitation.add(self.belong,another) # 棋盘模拟
                vertex = Vertex(imitation,not self.belong,self.player,self.round,parent = self) # 各种参数设置
                self.child[another]=vertex # 建立子节点关联
                vertex.mode = 'position' if self.belong else 'direction' # 模式设置
            for pos in available:
                imitation = self.board.copy()
                imitation.add(self.belong,pos)
                vertex = Vertex(imitation,not self.belong,self.player,self.round,parent = self)
                self.child[pos]=vertex
                vertex.mode = 'position' if self.belong else 'direction'
            if self.child == {}: # 考虑到无棋可走的可能
                imitation = self.board.copy()
                vertex = Vertex(imitation,not self.belong,self.player,self.round,parent = self)
                self.child[()]=vertex
                vertex.mode = 'position' if self.belong else 'direction'
            if self.player.belong == self.belong: # 按静态估值进行排序。
                self.orderedMove = sorted(self.child,key=lambda x: self.child[x].boardValue, reverse = True)
            else:
                self.orderedMove = sorted(self.child,key=lambda x: self.child[x].boardValue, reverse = False) 
        elif self.mode == 'direction':
            directionList = [0, 1, 2, 3]
            for direction in directionList:
                imitation = self.board.copy()
                if imitation.move(self.belong, direction):
                    vertex = Vertex(imitation,not self.belong,self.player,self.round,parent = self)
                    self.child[direction]=vertex
                    vertex.mode = 'direction' if self.belong else 'position'
                    vertex.round += 0 if self.belong else 1 # 如果是后手，子节点回合数将+1
            if self.child == {}:
                imitation = self.board.copy()
                vertex = Vertex(imitation,not self.belong,self.player,self.round,parent = self)
                self.child[()]=vertex
                vertex.mode = 'direction' if self.belong else 'position'
                vertex.round += 0 if self.belong else 1
            if self.player.belong == self.belong:
                self.orderedMove = sorted(self.child,key=lambda x: self.child[x].boardValue, reverse = True)
            else:
                self.orderedMove = sorted(self.child,key=lambda x: self.child[x].boardValue, reverse = False) 
        else:
            return
    def search(self,depth):
        '''相应深度的alpha-beta搜索，同时返回搜索有效性。'''
        if depth >= 1:
            self.expand() # 生成子节点
            bestchoice = None
            for move in self.orderedMove:
                self.child[move].setRange(self.alpha,self.beta)
                if self.child[move].search(depth - 1): # 递归地深度搜索
                    if self.player.belong == self.belong:
                        self.alpha = self.child[move].searchValue
                    else:
                        self.beta = self.child[move].searchValue
                    bestchoice = move
                if self.alpha >= self.beta: # 这里是大于等于，意味着相同估值时，先遍历的优先。
                    return False # 此时搜索无效
            if bestchoice is None: # 此时没有更优选择，搜索也算无效
                return False
            self.bestchoice = bestchoice
            if self.player.belong == self.belong:
                self.searchValue = self.alpha
            else:
                self.searchValue = self.beta
            return True
        elif depth == 0: # 递归的最简情况
            if self.player.belong == self.belong:
                self.alpha = self.boardValue
            else:
                self.beta = self.boardValue
            if self.alpha >= self.beta:
                return False
            else:
                self.searchValue = self.boardValue
                return True
        else:
            return False
def output(self, currentRound, board, mode):
    self.searchTree = Vertex(board,self.belong,self,currentRound,mode,parent=None)
    depth = 2 # 设置为正数，否则将返回None
    self.searchTree.search(depth)
    return self.searchTree.bestchoice
